package my.jwds.p90;

import com.alibaba.fastjson.JSONObject;

import java.util.ArrayList;
import java.util.List;

public class SubsetsWithDup {

    public static void main(String[] args) {
        SubsetsWithDup obj = new SubsetsWithDup();

        int [] nums = JSONObject.parseObject("[1,2,3]",int[].class);

        long start = System.currentTimeMillis();
        System.out.println(obj.subsetsWithDup(nums));
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        int[] s = new int[21];
        for (int num : nums) {
            s[num+10] ++;
        }

        List<List<Integer>> res = new ArrayList<>();
        bfs(res,s,new ArrayList<>(),0);

        return res;
    }

    void bfs(List<List<Integer>> res,int[] s,List<Integer> item,int start){
        res.add(new ArrayList<>(item));
        for (int i = start; i < s.length; i++) {
            if (s[i] != 0){
                List<Integer> newItem = new ArrayList<>(item);
                for (int j = 0; j < s[i]; j++) {
                    newItem.add(i - 10);
                    bfs(res, s, newItem, i+1);
                }
            }
        }

    }

}